package conclusion;

public class MathTricks {

	/**
	 * gcd(a, b) = gcd(b, a % b)
	 * if(a % b == 0) b is the gcd
	 * @param a
	 * @param b
	 * @return
	 */
	public static int greatestCommonDivisor(int a, int b){
		if(b == 0) return a;
		return greatestCommonDivisor(b, a % b);
	}
	
	public static int gcdIterative(int a, int b){
		while(b != 0){
			int temp = b;
			b = a % b;
			a = b;
		}
		return a;
	}
	
	public static int gcd2(int a, int b){//based on minus
		while(a != b){
			if(a > b) a -= b;
			else b-= a;
		}
		return a;
	}
	
	/**
	 * 1 is not prime
	 * @param n
	 * @return
	 */
	public static boolean isPrime(int n){
		if(n < 2) return false;
		
		int upper = (int) Math.sqrt(n);
		for(int i = 2 ; i <= upper ; i++){
			if(n % i == 0) return false;
		}
		return true;
	}
	/**
	 * Without using sqrt
	 * @param n
	 * @return
	 */
	public static boolean isPrime1(int n){
		if(n < 2) return false;
		for(int i = 2 ; i * i <= n ; i++){
			if(n % i == 0) return false;
		}
		return true;
	}
	
	//public static boolean isPrime2(int n){
		
	//}
	
	/**
	 * Method:
	 * when calculation pow(x,y) % z without pow
	 * if x^y is very huge, we cannot calculate x^y first because it leads to overflow.
	 * so, we use this: x^y%z = (x^(y1)%z) * (x^(y2)%z) % z
	 * @param x
	 * @param y
	 * @param z
	 * @return
	 */
	public static int calculateXpowYmodZwithoutPow(int x, int y, int z){
		if(z == 0 || y < 0) return -1;
		if(y == 1) return x%z;
		if(y == 0) return 1%z;
		else{
			int y1 = y/2;
			int y2 = y - y1;
			return calculateXpowYmodZwithoutPow(x, y1, z) * calculateXpowYmodZwithoutPow(x, y2, z) % z;
		}
	}
	
	
	public static void main(String[] args) {
		System.out.println(isPrime(2));
	}

}
